package leetcode.weekly.week340;

import java.util.Arrays;

//Solution3Test
public class Solution3 {

	public int minimizeMax(int[] nums, int p) {
		int l = 0, r = 1000000000;// 1000000000
		int ans = Integer.MAX_VALUE;
		Arrays.sort(nums);
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			int cnt = 0, last = -1;
			for (int i = 1; i < nums.length; i++) {
				if (last == i || i - 1 == last) {
					continue;
				}
				if (nums[i] - nums[i - 1] <= m) {
					cnt++;
					last = i;
				}
			}
			if (cnt >= p) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}
}
